#include<iostream>
#include<vector>
#include<queue>
using namespace std;

// 链表
struct ListNode{
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int val) : val(val), next(nullptr) {}
    ListNode(int val, ListNode* next) : val(val), next(next) {}
};

// 二叉树--孩子兄弟表示法
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
    TreeNode(int val, TreeNode *left, TreeNode *right): val(val), left(left), right(right) {}
};
// 二叉树的最大深度
class Solution {
public:
    int maxLevel = 0;
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        this->dfs(root, 1);
        return this->maxLevel;
    }
    void dfs(TreeNode* root, int level) {
        if (!root) return;

        // 先根遍历
        if (level > this->maxLevel) level = this->maxLevel;
        // 可以不要这个判断，入口已经有检测了
        if (root->left) dfs(root->left, level+1);
        if (root->right) dfs(root->right, level+1);
        return;
    }
};
// 二叉树的最大深度---递归版
class Solution {
public:
    int maxLevel = 0;
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        return max(left, right) + 1;
    }

};

// BFS---广度优先遍历
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root) que.push(root);
        vector<vector<int>> result;
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;

            for (int i=0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }

};

int main(int argc, char** argv) {
    return 0;
}